package com.jz.algorithm.Recursion;

import org.junit.Test;

/**
 * @Classname Recursion
 * @Description 递归的相关题目
 * @Date 2021/10/18 16:32
 * @Author Jz
 * @Version 1.0
 */
public class Recursion {

    /**
     * @Methodname test01
     * @Description 求x的n次方
     * @Date 2021/10/18 16:33
     * @Created by
     * @Return
     * @Param
     */
    @Test
    public static int  test01(int x,int n){
        if(n==0){
            return 1;
        }
        int t = test01(x, n / 2);

        if (n % 2 ==1 ){
            return t*t*x;
        }
        return  t*t;


    }
    /**
     * @Methodname fibonacci
     * @Description 求斐波那契第n项值
     * @Date 2021/10/18 17:23
     * @Created Jz
     * @Return 
     * @Param 
     */
    public  static  int fibonacci(int first, int second, int n) {
        if (n <= 0) {
            return 0;
        }
        if (n < 3) {
            return 1;
        }
        else if (n == 3) {
            return first + second;
        }
        else {
            return fibonacci(second, first + second, n - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(test01(2, 9));
        int fibonacci = fibonacci(1, 1, 9);
        System.out.println(fibonacci);
    }
}
